/**
 * 该模块提供实现 IMap(TKey, TValue) 接口的高性能无序 Map 集合。
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */
 
module system.collections.HashMap;

import system.collections.IEnumerable;
import system.collections.IEnumerator;
import system.collections.ICollection;
import system.collections.IMap;
import system.collections.IEqualityComparer;
import system.collections.Pair;
import system.collections.EqualityComparer;
import system.collections.Exception;
import system.collections.HashSet;
import PrimeHelper = system.collections.PrimeHelper;

import system.Array;
import system.Traits;
import system.Exception;

/**
 * 表示键和值的集合。
 * 它是实现了 IMap(TKey, TValue) 接口的高性能无序 Map 集合。
 * Params:
 *		TKey = 表示 Map 中键的类型；
 *		TValue = 表示 Map 中值的类型。
 * Comments:
 *		HashMap(TKey, TValue) 泛型类提供了从一组键到一组值的映射。
 *		HashMap(TKey, TValue) 中的每个添加项都由一个值及其相关联的键组成。
 *		通过键来检索值的速度非常快，接近于 O(1)，这是因为 HashMap(TKey, TValue) 类由哈希表实现。
 *
 *		Note : 此类不保证 Map 的顺序，特别是它不保证该顺序恒久不变。
 *			   检索速度取决于为 TKey 类型的哈希算法质量。
 *
 * 		只要对象用作 HashMap(TKey, TValue) 中的键，它就不能以任何影响其哈希值的方式更改。
 *		使用 Map 的相等比较器比较时，HashMap(TKey, TValue) 中的任何键都必须是唯一的。
 *		键不能为 null ，但是如果值类型 TValue 为引用类型，该值则可以为 null 。
 * 
 *		Note : 您可以使用 StringComparer 类提供的不区分大小写的字符串比较器来创建带不区分大小写的字符串键的 HashMap 。
 *
 *		HashMap(TKey, TValue) 的容量是 HashMap(TKey, TValue) 可以包含的元素数。
 *		当向 HashMap(TKey, TValue) 中添加元素时，将通过重新分配内部数组来根据需要自动增大容量。 
 *
 *		对于枚举而言，Map 中的每一项都被视为一个表示值及其键的 Pair(TKey, TValue) 结构进行处理。
 *		
 *		Note : 由于键可以被继承而且它们的行为已更改，因此使用 opEquals 方法进行的比较并不能保证其绝对唯一性。
 */

public class HashMap(TKey, TValue) : IEnumerable!(Pair!(TKey, TValue)), ICollection!(Pair!(TKey, TValue)), IMap!(TKey, TValue)
{
	package struct Slot
	{
		hash_t hashCode;
		int next;
		TKey key;
		TValue value;
	}

	private IEqualityComparer!(TKey) theComparer;
	private int[] theBuckets;
	private Slot[] theSlots;
	private int theSize;
	private int theFreeList;
	private int theFreeSize;
	private int theVersion;

	private KeyCollection theKeys;
	private ValueCollection theValues;

	/**
	 * 初始化 HashMap(TKey, TValue) 类的新实例，该实例为空且具有默认的初始容量，
	 * 并使用指定的 IEqualityComparer(TKey) 比较器。
     * 默认采用 DefaultEqualityComparer(TKey) 比较器。
	 * Params:
	 *		comparer = 指定的比较器。
	 * Throws:
	 *		AssertError，当 comparer 为 null 时。
	 * Comments:
	 *		使用带有 StringComparer 类提供的不区分大小写字符串比较器的此构造函数来创建带有不区分大小写的字符串键的 Map 。
	 *		使用指定的比较器比较时，HashMap(TKey, TValue) 中的所有键都必须是唯一的。
	 *
	 *		Note:
	 *			如果可以估计集合的大小，则可以使用指定初始容量的构造函数，
	 *			这样在向 HashMap(TKey, TValue) 中添加元素时可省去大量的扩容操作。
	 *
	 *		此构造函数的运算复杂度为 O(1)。 
	 */
	public this(IEqualityComparer!(TKey) comparer = DefaultEqualityComparer!(TKey).getInstance())
	in
	{
		assert(comparer !is null);
	}
	body
	{
		theComparer = comparer;
		theFreeList = -1;
	}

	/**
	 * 初始化 HashMap(TKey, TValue) 类的新实例，该实例为空且具有指定的初始容量，
	 * 并使用指定的 IEqualityComparer(TKey) 比较器。
	 * 默认采用 DefaultEqualityComparer(TKey) 比较器。
	 * Params:
	 *		capacity = 指定的初始容量。
	 *		comparer = 指定的比较器。
	 * Throws:
	 *		AssertError，当 comparer 为 null 或 capacity 小于 0 时。
	 * Comments:
	 *		使用带有 StringComparer 类提供的不区分大小写字符串比较器的此构造函数来创建带有不区分大小写的字符串键的 Map 。
	 *		使用指定的比较器比较时，HashMap(TKey, TValue) 中的所有键都必须是唯一的。
	 *
	 *		Note:
	 *			如果可以估计集合的大小，则可以使用指定初始容量的构造函数，
	 *			这样在向 HashMap(TKey, TValue) 中添加元素时可省去大量的扩容操作。
	 *
	 *		此构造函数的运算复杂度为 O(1)。 
	 */
	public this(int capacity, IEqualityComparer!(TKey) comparer = DefaultEqualityComparer!(TKey).getInstance())
	in
	{
		assert(capacity >= 0 && capacity <= int.max);
		assert(comparer !is null);
	}
	body
	{
		theComparer = comparer;
		theFreeList = -1;
		initialize(capacity);
	}

	/**
	 * 初始化 HashMap(TKey, TValue) 类的新实例，
	 * 该实例包含从指定的 IMap(TKey, TValue) 中复制的元素并使用指定的 IEqualityComparer(Pair!(TKey, TValue))。
	 * Params:
	 *		map = 要添加的 Map 集合。
	 *		comparer = 指定的比较器。
	 * Throws:
	 *		AssertError，当 map 为 null 或 comparer 为 null 时。
	 */
	public this(IMap!(TKey, TValue) map, IEqualityComparer!(TKey) comparer = DefaultEqualityComparer!(TKey).getInstance())
	in
	{
		assert(map !is null);
		assert(comparer !is null);
	}
	body
	{
		auto size = map.count;
		this(count, comparer);
		foreach(item; map)
		{
			this.add(item);
		}
		if((theSize == 0 && theSlots.length > PrimeHelper.PrimeArray[0]) || (theSize > 0 && (theSlots.length / theSize) > 3))
		{
			trimExcess();
		}
	}

	/*
	 * 实现 ICollection(T) 接口。
	 */

	/**
	 * 查看该 Map 是否为空。
	 * Returns:
	 *		假如该 Map 为空，返回 true；否则，返回 false。
	 * Comments:
	 *		该方法时间复杂度为 O(1)。
	 */
	public final bool isEmpty()
	{
		return theSize is 0;
	}

	/**
	 * 查看该 Map 是否为只读。
	 * Returns:
	 *		返回 false。
	 * Comments:
	 *		该方法时间复杂度为 O(1)。
	 */
	public final bool isReadOnly()
	{
		return false;
	}

	/**
	 * 获取该 Map 所包含的元素数。
	 * Returns:
	 *		返回该 Map 所包含的元素数。
	 * Comments:
	 *		该方法时间复杂度为 O(1)。
	 */
	public final int count()
	{
		return theSize;
	}

	/**
	 * 将指定的键-值对添加到此 HashMap(TKey, TValue) 中。
	 * Params:
	 *		item = 要添加的键-值对。
	 * Returns:
	 *		添加成功，返回 true；假如已存在该键-值对，则返回 false。
	 * Throws:
	 *		AssertError，当该键-值对的键为 null 时。
	 * Comments:
	 *		如果 count 小于容量，则此方法的运算复杂度为 O(1)。
	 *		如果需要增加容量以容纳新元素，则此方法的运算复杂度成为 O(n)，其中 n 为 count。 
	 */
	public final bool add(Pair!(TKey, TValue) item)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(item.key !is null);
		}
	}
	body
	{
		return this.insert(item.key, item.value);
	}

	/**
	 * 清空此 HashMap(TKey, TValue) 中的所有元素。
	 * Comments:
	 *		count 属性被设置为 0，并且集合中的元素对其他对象的引用也被释放。
	 *		容量保持不变。 
	 *
	 *		此方法的运算复杂度为 O(n)，其中 n 是字典的容量。
	 */
	public final void clear()
	{
		if(theFreeSize > 0)
		{
			Array.clear!(Slot)(theSlots[0..theFreeSize]);
			Array.clear!(int)(theBuckets);
			theSize = 0;
			theFreeSize = 0;
			theFreeList = -1;
		}
		theVersion++;
	}

	/**
	 * 确定此 HashMap(TKey, TValue) 是否包含特定的键和值。
	 * Params:
	 *		item = 要在此 HashMap(TKey, TValue) 中查找的键-值对。
	 * Returns:
	 *		如果包含，返回 true；否则，返回 false。
	 * Throws:
	 *		AssertError，当该键-值对的键为 null 时。
	 * Comments:
	 *		此方法的运算复杂度接近 O(1)。
	 */
	public final bool contains(Pair!(TKey, TValue) item)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(item.key !is null);
		}
	}
	body
	{
		auto index = indexOf(item.key);
		if(index != -1)
		{
			static if(IsReferenceType!(TValue))
			{
				if(item.value is null)
				{
					if(theSlots[index].value is null)
						return true;
				}
				else
				{
					return DefaultEqualityComparer!(TValue).getInstance().equals(item.value, theSlots[index].value);
				}
			}
			else
			{
				return DefaultEqualityComparer!(TValue).getInstance().equals(item.value, theSlots[index].value);
			}
		}
		return false;
	}

	/**
	 * 在此 HashMap(TKey, TValue) 中移除指定的键-值对。
	 * Params:
	 *		item = 要移除的键-值对。
	 * Returns:
	 *		如果移除成功，返回 true；否则返回false。
	 *		没有找到该键-值对，也返回 false。
	 * Throws:
	 *		AssertError，当该键-值对的键为 null 时。
	 */
	public final bool remove(Pair!(TKey, TValue) item)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(item.key !is null);
		}
	}
	body
	{
		auto index = indexOf(item.key);
		if(index != -1)
		{
			static if(IsReferenceType!(TValue))
			{
				if(item.value is null)
				{
					if(theSlots[index].value is null)
					{
						this.remove(item.key);
						return true;
					}
				}
				else
				{
					if(DefaultEqualityComparer!(TValue).getInstance().equals(item.value, theSlots[index].value))
					{
						this.remove(item.key);
						return true;
					}
				}
			}
			else
			{
				if(DefaultEqualityComparer!(TValue).getInstance().equals(item.value, theSlots[index].value))
				{
					this.remove(item.key);
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * 将此 HashMap(TKey, TValue) 中的所有元素移动到指定的键-值对数组中。
	 * Params:
	 *		array = 指定的目标数组。
	 * Throws:
	 *		AssertError，当 array 为 null 或 array 的长度小于此 Map 的元素数时。
	 * Comments:
	 *		此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final void toArray(Pair!(TKey, TValue)[] array)
	in
	{
		assert(array !is null);
		assert(array.length >= theSize, "The array is too small.");
	}
	body
	{
		auto size = 0;
		for(auto i = 0; i < theFreeSize && size < theSize; i++)
		{
			if(theSlots[i].hashCode >= 0)
			{
				array[size++] = Pair!(TKey, TValue)(theSlots[i].key, theSlots[i].value);
			}
		}
	}

	/*
	 * 实现 IEnumerable(Pair!(TKey, TValue)) 接口。
	 */

	public final IEnumerator!(Pair!(TKey, TValue)) getEnumerator()
	{
		return new Enumerator();
	}

	public final int opApply (int delegate (ref Pair!(TKey, TValue) value) dg)
	{
		auto scope enumerator = new Enumerator();
        int result = 0;
		while( enumerator.moveNext() )
		{
			auto value = enumerator.current();
			if( (result = dg(value) ) != 0 )
				break;
		}
		return result;
	}

	public final int opApply(int delegate(ref TKey, ref TValue) dg)
	{
		auto scope iterator = new Enumerator();
		int result = 0;
		while(iterator.moveNext())
		{
			auto pair = iterator.current();
			auto key = pair.key;
			auto value = pair.value;
			if( (result = dg(key, value)) != 0 )
				break;
		}
		return result;
	}

	public final class Enumerator : IEnumerator!(Pair!(TKey, TValue))
	{
		private int theIndex;
		private int modCount;
		private Pair!(TKey, TValue) theValue;

		package this()
		{
			theIndex = 0;
			modCount = theVersion;
			theValue = (Pair!(TKey, TValue)).init;
		}

		public bool moveNext()
		{
			if(modCount != theVersion)
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");

			while(theIndex < theFreeSize)
			{
				if(theSlots[theIndex].hashCode >= 0)
				{
					theValue = Pair!(TKey, TValue)(theSlots[theIndex].key, theSlots[theIndex].value);
					theIndex++;
					return true;
				}
				theIndex++;
			}

			theIndex = theFreeSize + 1;
			theValue = (Pair!(TKey, TValue)).init;
			return false;
		}

		public Pair!(TKey, TValue) current()
		{
			return theValue;
		}

		public void reset()
		{
			if(modCount != theVersion)
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");

			theIndex = 0;
			theValue = (Pair!(TKey, TValue)).init;
		}
	}


	/*
	 * 实现 IMap(TKey, TValue) 接口。
	 */

	/**
	 * 将指定的键和值添加到此 HashMap(TKey, TValue) 中。
	 * Params:
	 *		key = 要添加的键。
	 *		value = 要添加的值。
	 * Throws:
	 *		AssertError，当 key 为 null 时。
	 * Comments:
	 *		键不能为 null，但是如果 TValue 为引用类型，值则可以为空。
	 *		如果 count 小于容量，则此方法的运算复杂度为 O(1)。
	 *		如果需要增加容量以容纳新元素，则此方法的运算复杂度成为 O(n)，其中 n 为 count。 
	 */
	public final void add(TKey key, TValue value)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		this.insert(key, value);
	}

	/**
	 * 确定此 HashMap(TKey, TValue) 是否包含指定的键。
	 * Params:
	 *		key = 要查找的键。
	 * Returns:
	 *		如果包含，返回 true；否则返回 false。
	 * Throws:
	 *		AssertError，当 key 为 null 时。
	 * Comments:
	 *		此方法的运算复杂度接近 O(1)。
	 */
	public final bool containsKey(TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		return indexOf(key) != -1;
	}

	/**
	 * 确定此 HashMap(TKey, TValue) 是否包含指定的值。
	 * Params:
	 *		value = 要查找的值。对于引用类型，该值可以为 null。
	 * Returns:
	 *		如果包含，返回 true；否则返回 false。
	 * Comments:
	 *		此方法使用默认的相等比较器 DefaultEqualityComparer(TValue) 来确定 TValue 是否相等。
	 *		此方法执行线性搜索，因此平均执行时间与 count 成比例。
	 *		即，此方法的运算复杂度为 O(n)，其中 n 为 count。
	 */
	public final bool containsValue(TValue value)
	{
		auto comparer = DefaultEqualityComparer!(TValue).getInstance();
		static if(IsReferenceType!(TValue))
		{
			if(value is null)
			{
				for(auto i = 0; i < theFreeSize ; i++)
				{
					if((theSlots[i].hashCode >= 0) && (theSlots[i].value is null))
					{
						return true;
					}
				}
			}
			else
			{
				for(auto i = 0; i < theFreeSize ; i++)
				{
					if((theSlots[i].hashCode >= 0) && (comparer.equals((theSlots[i].value), value)))
					{
						return true;
					}
				}
			}
		}
		else
		{
			for(auto i = 0; i < theFreeSize ; i++)
			{
				if((theSlots[i].hashCode >= 0) && comparer.equals(theSlots[i].value, value))
				{
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * 从此 HashMap(TKey, TValue) 中移除指定的键的值。
	 * Params:
	 *		key = 要移除的值的键。
	 * Returns:
	 *		移除成功，返回 true；否则，返回 false。
	 *		查找不到该值，也返回 false。
	 * Throws:
	 *		AssertError，当 key 为 null 时。
	 * Comments:
	 *		此方法的运算复杂度接近 O(1)。 
	 */
	public final bool remove(TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		if(theBuckets !is null)
		{
			auto hash = hashOf(key);
			auto index = hash % theBuckets.length;
			auto freeList = -1;
			for(auto i = theBuckets[index] - 1; i >= 0; i = theSlots[i].next)
			{
				if((theSlots[i].hashCode == hash) && (comparer.equals(theSlots[i].key, key)))
				{
					if(freeList < 0)
					{
						theBuckets[index] = theSlots[i].next + 1;
					}
					else
					{
						theSlots[freeList].next = theSlots[i].next;
					}
					theSlots[i].hashCode = -1;
					theSlots[i].next = theFreeList;
					theSlots[i].key = TKey.init;
					theSlots[i].value = TValue.init;
					theFreeList = i;
					theSize--;
					theVersion++;
					return true;
				}
				freeList = i;
			}
		}
		return false;
	}

	/**
	 * 获取与指定的键相关联的值。 
	 * Params:
	 *		key = 要获取的值的键。
	 *		value = 当此方法返回值时，如果找到该键，便会返回与指定的键相关联的值；
	 *				 否则，则会返回 value 参数的类型默认值。
	 *				 out 属性。
	 * Returns:
	 *		如果包含具有指定键的元素，则为 true；否则为 false。
	 * Throws:
	 *		AssertError，当 key 为 null 时。
	 * Comments:
	 *		假如代码频繁尝试访问 Map 中不存在的键，则可使用该方法。
	 *		该方法不引发异常。比起索引器方法会引发 KeyNotFoundException 来说该方法更加有效。
	 *		此方法的运算复杂度接近 O(1)。 
	 */
	public final bool tryGetValue(TKey key, out TValue value)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		auto index = indexOf(key);
		if(index >= 0)
		{
			value = theSlots[index].value;
			return true;
		}
		value = TValue.init;
		return false;
	}

	/**
	 * 索引器。
	 */
	 
	public final TValue opIndex(TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		auto index = indexOf(key);
		if(index >= 0)
		{
			return theSlots[index].value;
		}
		throw new KeyNotFoundException("The key is not found.");
		return TValue.init;
	}

	public final void opIndexAssign(TValue value, TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null, "The key can not be null.");
		}
	}
	body
	{
		this.add(key, value);
	}

	/*
	 * 其他方法
	 */
	 
	/**
	 * 返回此 Map 所使用的比较器。
	 */
	public final IEqualityComparer!(TKey) comparer()
	{
		return theComparer;
	}

	/**
	 * 获取此 Map 中键的集合。
	 * Comments:
	 *		返回的 HashMap(TKey, TValue).KeyCollection 不是静态副本；
	 *		相反，HashMap(TKey, TValue).KeyCollection 反向引用原始 HashMap(TKey, TValue) 中的键。
	 *		因此，对 HashMap(TKey, TValue) 的更改将继续反映到 HashMap(TKey, TValue).KeyCollection 中。 
	 *
	 *	获取此属性的值的运算复杂度为 O(1)。 
	 */
	public final KeyCollection keys()
	{
		if(theKeys is null)
		{
			theKeys = new KeyCollection(this);
		}
		return theKeys;
	}

	/**
	 * 获取此 Map 中值的集合。
	 * Comments:
	 *		返回的 HashMap(TKey, TValue).ValueCollection 不是静态副本；
	 *		相反，HashMap(TKey, TValue).ValueCollection 反向引用原始 HashMap(TKey, TValue) 中的值。
	 *		因此，对 HashMap(TKey, TValue) 的更改将继续反映到 HashMap(TKey, TValue).ValueCollection 中。 
	 *
	 *	获取此属性的值的运算复杂度为 O(1)。
	 */
	public final ValueCollection values()
	{
		if(theValues is null)
		{
			theValues = new ValueCollection(this);
		}
		return theValues;
	}

	/**
	 * 将 HashMap(TKey, TValue) 的容量设置为它所包含的元素的实际个数，
	 * 向上舍入为接近的特定于实现的值。
	 * Comments:
	 *		如果已知不会再添加新元素，
	 *		可以使用 trimExcess 方法将 HashMap(TKey, TValue) 的内存开销降到最低限度；
	 *		若要彻底清除 HashMap(TKey, TValue) 并释放它引用的所有内存，
	 *		请在调用 Clear 方法后再调用此方法。 
	 *		此方法的运算复杂度为 O(n)，其中 n 为 count。
	 */
	public final void trimExcess()
	{
		if(theSize == 0)
		{
			if(theBuckets !is null)
				delete theBuckets;
			if(theSlots !is null)
				delete theSlots;
			theVersion++;
		}
		else
		{
			auto newPrime = PrimeHelper.getNextPrime(theSize);
			auto newSlots = new Slot[newPrime];
			auto newBuckets = new int[newPrime];
			int index = 0;
			for(auto i = 0; i < theFreeSize; i++)
			{
				if(theSlots[i].hashCode >= 0)
				{
					newSlots[index] = theSlots[i];
					auto bucket = newSlots[index].hashCode % newPrime;
					newSlots[index].next = newBuckets[bucket] - 1;
					newBuckets[bucket] = index + 1;
					index++;
				}
			}
			theFreeSize = index;
			delete theSlots;
			delete theBuckets;
			theSlots = newSlots;
			theBuckets = newBuckets;
			theFreeList = -1;
		}
	}

	public class KeyCollection : ICollection!(TKey), IEnumerable!(TKey)
	{
		private HashMap!(TKey, TValue) theMap;
		
		public this(HashMap!(TKey, TValue) map)
		{
			theMap = map;
		}
		/*
		 * 实现 IEnumerable(TKey) 接口。
		 */

		public IEnumerator!(TKey) getEnumerator()
		{
		    return new KeysEnumerator();
		}

		public int opApply (int delegate (ref TKey value) dg)
		{
			auto scope enumerator = new KeysEnumerator();
			int result = 0;
			while( enumerator.moveNext() )
			{
				auto value = enumerator.current();
				if( (result = dg(value) ) != 0 )
					break;
			}
			return result;
		}

		public class KeysEnumerator : IEnumerator!(TKey)
		{
			private IEnumerator!(Pair!(TKey, TValue)) theIterator;

			public this()
			{
				theIterator = theMap.getEnumerator();
			}

			public bool moveNext()
			{
				return theIterator.moveNext();
			}

			public TKey current()
			{
				return theIterator.current.key;
			}

			public void reset()
			{
				theIterator.reset();
			}
		}

		/*
		 * 实现 ICollection(TKey) 接口。
		 */

		public bool isEmpty()
		{
			return theMap.isEmpty();
		}

		public int count()
		{
			return theMap.count();
		}

		public bool add(TKey key)
		{
			throw new NotSupportedException();
			return false;
		}

		public bool isReadOnly()
		{
			return true;
		}

		public void clear()
		{
			throw new NotSupportedException();
		}

		public bool remove(TKey key)
		{
			throw new NotSupportedException();
			return false;
		}

		public bool contains(TKey key)
		{
			return theMap.containsKey(key);
		}

		public void toArray(TKey[] array)
		in
		{
			assert( array !is null );
			assert( array.length >= this.count(), "The length of array is too small." );
		}
		body
		{
			auto index = 0;
			foreach(pair; theMap)
			{
				array[index++] = pair.key;
			}
		}
	}

	/**
	 * 获取包含 TreeMap(TKey, TValue) 中的值的集合。
	 * TreeMap(TKey, TValue).ValueCollection 中的值根据 comparer 属性进行排序，
	 * 并且与 keys 属性所返回的 TreeMap(TKey, TValue).KeyCollection 中的关联键具有相同的顺序。
	 *
	 * 返回的 TreeMap(TKey, TValue).ValueCollection 不是静态副本；
	 * 相反，TreeMap(TKey, TValue).ValueCollection 反向引用原始 TreeMap(TKey, TValue) 中的值。
	 * 因此，对 TreeMap(TKey, TValue) 的更改将继续反映到 TreeMap(TKey, TValue).ValueCollection 中。
	 */
	public class ValueCollection : IEnumerable!(TValue), ICollection!(TValue)
	{
		private HashMap!(TKey, TValue) theMap;
		
		public this(HashMap!(TKey, TValue) map)
		{
			theMap = map;
		}

		/*
		 * 实现 IEnumerable(TValue) 接口。
		 */

		public IEnumerator!(TValue) getEnumerator()
		{
			return new ValuesEnumerator();
		}

		public int opApply (int delegate (ref TValue value) dg)
		{
			auto scope enumerator = new ValuesEnumerator();
			int result = 0;
			while( enumerator.moveNext() )
			{
				auto value = enumerator.current();
				if( (result = dg(value) ) != 0 )
					break;
			}
			return result;
		}

		public class ValuesEnumerator : IEnumerator!(TValue)
		{
			private IEnumerator!(Pair!(TKey, TValue)) theIterator;

			public this()
			{
				theIterator = theMap.getEnumerator();
			}

			public bool moveNext()
			{
				return theIterator.moveNext();
			}

			public TValue current()
			{
				return theIterator.current.value;
			}

			public void reset()
			{
				theIterator.reset();
			}
		}

		/*
		 * 实现 ICollection(TValue) 接口。
		 */

		public bool isEmpty()
		{
			return theMap.isEmpty();
		}

		public int count()
		{
			return theMap.count();
		}

		public bool add(TValue value)
		{
			throw new NotSupportedException();
			return false;
		}

		public bool isReadOnly()
		{
			return true;
		}

		public void clear()
		{
			throw new NotSupportedException();
		}

		public bool remove(TValue value)
		{
			throw new NotSupportedException();
			return false;
		}

		public bool contains(TValue value)
		{
			return theMap.containsValue(value);
		}

		public void toArray(TValue[] array)
		in
		{
			assert( array !is null );
			assert( array.length >= this.count(), "The length of array is too small." );
		}
		body
		{
			auto index = 0;
			foreach(pair; theMap)
			{
				array[index++] = pair.value;
			}
		}
	}

	private void initialize(int size)
	{
		auto newSize = PrimeHelper.getNextPrime(size);
		theBuckets = new int[newSize];
		theSlots = new Slot[newSize];
	}

	private void resize()
	{
		int newSize = theSize * 2;
		if(newSize < 0)
			newSize = theSize;
		auto prime = PrimeHelper.getNextPrime(newSize);
		if(prime <= theSize)
			throw new ArgumentException("The set is overflow.");
		if(theSlots !is null)
		{
			theSlots.length = prime;
		}
		auto newBuckets = new int[prime];
		for(auto i = 0; i < theFreeSize; i++)
		{
			auto index = theSlots[i].hashCode % prime;
			theSlots[i].next = newBuckets[index] - 1;
			newBuckets[index] = i + 1;
		}
		delete theBuckets;
		theBuckets = newBuckets;
	}

	private hash_t hashOf(TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		return theComparer.toHash(key) & int.max;
	}


	private int indexOf(TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		auto hash = hashOf(key);
		auto index = hash % theBuckets.length;
		for(auto i = theBuckets[index] - 1; i >= 0; i = theSlots[i].next)
		{
			if((theSlots[i].hashCode == hash) && (theComparer.equals(theSlots[i].key, key)))
			{
				return i;
			}
		}
		return -1;
	}

	private bool insert(TKey key, TValue value)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		int freeList;
		if(theBuckets is null)
		{
			initialize(3);
		}
		//计算该元素的哈希值和在哈希表内的索引位置
		auto hash = hashOf(key);
		auto index = hash % theBuckets.length;
		
		//查找是否哈希表内已经有该元素
		for(auto i = theBuckets[index] - 1; i >= 0; i = theSlots[i].next)
		{
			if(theSlots[i].hashCode == hash && theComparer.equals(theSlots[i].key, key))
			{
				static if(IsReferenceType!(TValue))
				{
					if(value is null)
					{
						if(theSlots[i].value is null)
							return false;
						else
						{
							theSlots[i].value = value;
							theVersion++;
							return true;
						}
					}
					else
					{
						if(DefaultEqualityComparer!(TValue).getInstance().equals(theSlots[i].value, value))
							return false;
						else
						{
							theSlots[i].value = value;
							theVersion++;
							return true;
						}
					}
				}
				else
				{
					if(DefaultEqualityComparer!(TValue).getInstance().equals(theSlots[i].value, value))
						return false;
					else
					{
						theSlots[i].value = value;
						theVersion++;
						return true;
					}
				}
			}
		}

		//到了这里，表明哈希表内没有该元素
		//但是引起了哈希表散列冲突
		if(theFreeList >= 0)
		{
			//查找元素放入链表的适当位置
			freeList = theFreeList;
			theFreeList = theSlots[freeList].next;
		}
		else	//没有引起哈希表散列冲突
		{
			//查看是否满载，是否需要扩容
			if(theFreeSize == theSlots.length)
			{
				resize();
				index = hash % theBuckets.length;
			}
			freeList = theFreeSize;
			theFreeSize++;
		}
		//把元素放入哈希表内
		//并设置合适的值
		theSlots[freeList].hashCode = hash;
		theSlots[freeList].next = theBuckets[index] - 1;
		theSlots[freeList].key = key;
		theSlots[freeList].value = value;

		theBuckets[index] = freeList + 1;

		theSize++;
		theVersion++;
		return true;
	}
}

unittest
{
	class MyClass
	{
		int a;
		int b;

		public this(int a, int b)
		{
			this.a = a;
			this.b = b;
		}

		public override hash_t toHash()
		{
			return a + b;
		}

		public override bool opEquals(Object obj)
		{
			auto result = cast(MyClass)obj;
			if(result is null)
				return false;
			return result.value == a;
		}

		public int value()
		{
			return a;
		}
	}
	
	class TestHashMap
	{
		private HashMap!(string, string) strMap;
		private HashMap!(MyClass, MyClass) objMap;
		private HashMap!(int, int) intMap;

		this()
		{
			strMap = new HashMap!(string, string)();
			objMap = new HashMap!(MyClass, MyClass)();
			intMap = new HashMap!(int, int)();
		}

		void testAdd()
		{
			strMap.add("Key", "Value");

			
			assert(strMap["Key"] == "Value");
			
			auto myA = new MyClass(10, 20);
			auto myB = new MyClass(20, 40);
			auto myC = new MyClass(12, 24);

			objMap.add(myA, myA);
			objMap.add(myB, myB);
			objMap.add(myC, myC);

			assert(objMap[myA].value == 10);
			assert(objMap[myB].value == 20);
			assert(objMap[myC].value == 12);

			intMap.add(1, 10);
			intMap.add(2, 20);
			intMap.add(3, 30);

			assert(intMap[1] == 10);
			assert(intMap[2] == 20);
			assert(intMap[3] == 30);

			try
			{
				strMap.add(null, "");
			}
			catch(AssertError e)
			{
				assert(true);
			}

			strMap.add("Key", "Value");

			assert(strMap.count == 1);

		}

		void testIndexer()
		{
			auto str = strMap["Key"];
			assert( str == "Value");
			try
			{
				str = strMap["Value"];
			}
			catch(KeyNotFoundException e)
			{
				assert(true);
			}
			strMap["Key"] = "Key1";
			assert(strMap["Key"] == "Key1");
			assert(!strMap.containsValue("Value"));
		}

		void testRemove()
		{
			strMap.clear();
			
			strMap.add("Key1", "Value1");
			strMap.add("Key2", "Value2");
			strMap.add("Key3", "Value3");

			assert(strMap.remove("Key3"));
			assert(!strMap.remove("Key4"));

			assert(strMap.count == 2);
			assert(!strMap.containsKey("Key3"));
			assert(!strMap.containsValue("Value3"));

			objMap.clear();

			auto myA = new MyClass(10, 5);
			auto myB = new MyClass(20, 5);
			auto myC = new MyClass(12, 3);

			objMap.add(myA, myA);
			objMap.add(myB, myB);
			objMap.add(myC, myC);

			objMap.remove(myA);

			assert(objMap.count == 2);
			assert(objMap[myB].value == 20);
			assert(!objMap.containsKey(myA));

			try
			{
				objMap[null] = myA;
			}
			catch(AssertError e)	
			{
				assert(true);
			}
		}

		void testClear()
		{
			intMap.add(1,1);
			intMap.add(2,2);
			intMap.add(3,3);

			intMap.clear();

			assert(intMap.isEmpty());
			assert(!intMap.containsKey(1));
			assert(!intMap.containsKey(2));
			assert(!intMap.containsKey(3));
		}

		void testContainsKey()
		{
			intMap.clear();
			
			intMap.add(1,1);
			intMap.add(2,2);

			assert(intMap.count == 2);
			assert(intMap.containsKey(1));
			assert(intMap.containsKey(2));
		}

		void testContainsValue()
		{
			intMap.clear();
			
			intMap.add(1,1);
			intMap.add(2,2);

			assert(intMap.count == 2);
			assert(intMap.containsValue(1));
			assert(intMap.containsValue(2));
		}

		void testTryGetValue()
		{
			intMap.clear();
			
			intMap.add(1,1);
			intMap.add(2,2);

			bool result;
			int value;

			result = intMap.tryGetValue(1, value);

			assert(result is true && value is 1);

			result = intMap.tryGetValue(4, value);

			assert(result is false && value is 0);
		}

		void testForEach()
		{
			intMap.clear();
			
			intMap.add(1,1);
			intMap.add(2,2);

			int result = 0;

			foreach(item; intMap)
			{
				result++;
			}

			assert(result is 2);

			foreach(key, value; intMap)
			{
				result++;
			}

			assert(result is 4);

			try
			{
				foreach(key, value; intMap)
				{
					intMap.add(4, 4);
				}
			}
			catch(InvalidOperationException e)
			{
				assert(true);
			}
		}

		void testResize()
		{
			auto map = new HashMap!(int, float)(3);

			map.add(1, 1.0F);
			map.add(2, 2.0F);
			map.add(3, 3.0F);

			assert(map.count == 3);

			map.add(4, 4.0F);

			assert(map[1] == 1.0F);
			assert(map[2] == 2.0F);
			assert(map[3] == 3.0F);
			assert(map[4] == 4.0F);

			map.trimExcess();

			assert(map[1] == 1.0F);
			assert(map[2] == 2.0F);
			assert(map[3] == 3.0F);
			assert(map[4] == 4.0F);
		}

		void testKeyCollection()
		{
			auto map = new HashMap!(int, float)(3);

			map.add(1, 1.0F);
			map.add(2, 2.0F);
			map.add(3, 3.0F);

			auto keys = map.keys;

			assert(keys.count == 3);

			auto result = 0;
			
			foreach(item; keys)
			{
				result++;
			}

			assert(result == 3);

			try
			{
				foreach(item; keys)
				{
					keys.add(4);
				}
			}
			catch(NotSupportedException e)
			{
				assert(true);
			}
		}

		void testValueCollection()
		{
			auto map = new HashMap!(int, float)(3);

			map.add(1, 1.0F);
			map.add(2, 2.0F);
			map.add(3, 3.0F);

			auto values = map.values;

			assert(values.count == 3);

			auto result = 0;
			
			foreach(item; values)
			{
				result++;
			}

			assert(result == 3);

			try
			{
				foreach(item; values)
				{
					values.add(4.0F);
				}
			}
			catch(NotSupportedException e)
			{
				assert(true);
			}
		}

		void testToArray()
		{
			auto map = new HashMap!(int, float)(3);
			auto array = [Pair!(int, float)(1,1.0F), Pair!(int, float)(2,2.0F), Pair!(int, float)(3,3.0F)];
			Pair!(int, float)[3] newArray = void;

			map.add(1, 1.0F);
			map.add(2, 2.0F);
			map.add(3, 3.0F);

			map.toArray(newArray);

			for(auto i = 0; i < newArray.length; i++)
			{
				assert(newArray[i] == array[i]);
			}
		}
	}

	auto test = new TestHashMap();
	test.testAdd();
	test.testIndexer();
	test.testRemove();
	test.testClear();
	test.testContainsKey();
	test.testContainsValue();
	test.testTryGetValue();
	test.testForEach();
	test.testResize();
	test.testKeyCollection();
	test.testValueCollection();
}